#include<iostream>
#include<vector>
using namespace std;

const int N=1e6;
bool primes[N];

auto Init=[]
{
    primes[1]=true;
    for(int i=2;i<=N/i;++i)
    {
        if(!primes[i])
            for(int j=i*i;j<N;j+=i)
                primes[j]=true;
    }
    return 0;
}();

class Solution {
public:
int dics[8][2]={{1,1},{1,-1},{-1,1},{-1,-1},{0,1},{0,-1},{1,0},{-1,0}};
int cnt[N];
int mc=0,res=-1;//mc
int m,n;
    void path(vector<vector<int>> mat,int i,int j)
    {
        for (auto dic : dics)
        {
            int x = i, y = j;
            int path = 0;
            while (x >= 0&&x < m &&y >=0 && y < n)
            {
                path = path * 10 + mat[x][y];
                ++cnt[path];
                if (path > 10 && !primes[path])
                {
                    if(cnt[path]==mc)
                    {
                        res=max(res,path);
                    }
                    else if(cnt[path]>mc)
                    {
                        mc=cnt[path];
                        res=path;
                    }
                }
                x += dic[0], y += dic[1];
            }
        }
    }

    int mostFrequentPrime(vector<vector<int>>& mat) {
        m=mat.size(),n=mat[0].size();
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
            {   
                path(mat,i,j);
            }
        }
        return res;
    }
};